{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Subarray Minimums"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #dynamic-programming #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #动态规划 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumSubarrayMins"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子数组的最小值之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组 <code>arr</code>，找到 <code>min(b)</code> 的总和，其中 <code>b</code> 的范围为 <code>arr</code> 的每个（连续）子数组。</p>\n",
    "\n",
    "<p>由于答案可能很大，因此<strong> 返回答案模 <code>10^9 + 7</code></strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [3,1,2,4]\n",
    "<strong>输出：</strong>17\n",
    "<strong>解释：\n",
    "</strong>子数组为<strong> </strong>[3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 \n",
    "最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [11,81,94,43,3]\n",
    "<strong>输出：</strong>444\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= arr.length <= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 <= arr[i] <= 3 * 10<sup>4</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-subarray-minimums](https://leetcode.cn/problems/sum-of-subarray-minimums/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-subarray-minimums](https://leetcode.cn/problems/sum-of-subarray-minimums/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1,2,4]', '[11,81,94,43,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        # ans=0\n",
    "        # n=len(arr)\n",
    "        # for i in range(n):\n",
    "        #     min_num=min(arr[i:])\n",
    "        #     min_index=i+arr[i:].index(min_num)\n",
    "        #     for j in range(i,n):\n",
    "        #         if j>=min_index:\n",
    "        #             ans += (n-j)*min_num\n",
    "        #             break\n",
    "        #         ans += min(arr[i:j+1])\n",
    "        # return ans%(10**9 + 7)\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        ret = tmpsum = 0\n",
    "        q = deque()\n",
    "        q.append(-1)\n",
    "        for idx,val in enumerate(arr):\n",
    "            while len(q)>1 and val<=arr[q[-1]]:\n",
    "                x = q.pop()\n",
    "                tmpsum -= (x-q[-1])*arr[x]\n",
    "            tmpsum += (idx-q[-1])*val\n",
    "            q.append(idx)\n",
    "            ret = (ret+tmpsum)%1000000007\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "\n",
    "        n = len(arr)\n",
    "        monoStack = []\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            while monoStack and x <= arr[monoStack[-1]]:\n",
    "                monoStack.pop()\n",
    "            left[i] = i - (monoStack[-1] if monoStack else -1)\n",
    "            monoStack.append(i)\n",
    "        monoStack = []\n",
    "        # print(left)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while monoStack and arr[i] < arr[monoStack[-1]]:\n",
    "                monoStack.pop()\n",
    "            right[i] = (monoStack[-1] if monoStack else n) - i\n",
    "            monoStack.append(i)\n",
    "        # print(right)\n",
    "        ans = 0\n",
    "        for l, r, x in zip(left, right, arr):\n",
    "            ans = (ans + l * r * x) % MOD\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "\t\tMOD = 10 ** 9 + 7\n",
    "\t\tn = len(arr)\n",
    "\t\tleft = [0] * n\n",
    "\t\tright = [0] * n\n",
    "\t\tstack = []\n",
    "\t\tres = 0\n",
    "\t\tfor i in range(n):\n",
    "\t\t\twhile stack and arr[i] <= arr[stack[-1]]:\n",
    "\t\t\t\tstack.pop()\n",
    "\t\t\tleft[i] = i - (stack[-1] if stack else -1)\n",
    "\t\t\tstack.append(i)\n",
    "\t\tstack = []\n",
    "\t\tfor i in range(n-1, -1, -1):\n",
    "\t\t\twhile stack and arr[i] < arr[stack[-1]]:\n",
    "\t\t\t\tstack.pop()\n",
    "\t\t\tright[i] = (stack[-1] if stack else n) - i\n",
    "\t\t\tstack.append(i)\n",
    "\t\tfor l, r, num in zip(left, right, arr):\n",
    "\t\t\tres = (res + l * r * num) % MOD\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        ret = tmpsum = 0\n",
    "        q = deque()\n",
    "        q.append(-1)\n",
    "        for idx,val in enumerate(arr):\n",
    "            while len(q)>1 and val<=arr[q[-1]]:\n",
    "                x = q.pop()\n",
    "                tmpsum -= (x-q[-1])*arr[x]\n",
    "            tmpsum += (idx-q[-1])*val\n",
    "            q.append(idx)\n",
    "            ret = (ret+tmpsum)%1000000007\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        monoStack=[]  #单调栈存储下标\n",
    "        ans,n=0,len(arr)\n",
    "        for i in range(n+1):\n",
    "            num=arr[i] if i<n else 0  #i==n时，弹出全部剩余元素\n",
    "            while monoStack and arr[monoStack[-1]]>num:\n",
    "                mid=monoStack.pop()  #arr[mid]为最小值的子数组区间：以 (head,mid]开头，[mid,tail)结尾\n",
    "                head=monoStack[-1] if monoStack else -1\n",
    "                tail=i\n",
    "                ans+=(mid-head)*(tail-mid)*arr[mid]\n",
    "            monoStack.append(i)\n",
    "        return ans%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_element(self, arr, idx):\n",
    "        if idx == -1 or idx == len(arr):\n",
    "            return float(\"-inf\")\n",
    "        return arr[idx]\n",
    "\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        if not arr:\n",
    "            return 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        mono_stack = []\n",
    "        for i in range(-1, n + 1):\n",
    "            while mono_stack and self.get_element(arr, mono_stack[-1]) > self.get_element(arr, i):\n",
    "                curr = mono_stack.pop()\n",
    "                ans = ((curr - mono_stack[-1]) * (i - curr) * arr[curr] + ans) % mod\n",
    "            mono_stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_element(self, arr, idx):\n",
    "        if idx == -1 or idx == len(arr):\n",
    "            return float(\"-inf\")\n",
    "        return arr[idx]\n",
    "\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        if not arr:\n",
    "            return 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        mono_stack = []\n",
    "        for i in range(-1, n + 1):\n",
    "            while mono_stack and self.get_element(arr, mono_stack[-1]) > self.get_element(arr, i):\n",
    "                curr = mono_stack.pop()\n",
    "                ans = ((curr - mono_stack[-1]) * (i - curr) * arr[curr] + ans) % mod\n",
    "            mono_stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        arr.append(-1)\n",
    "        ans, st = 0, [-1]  # 哨兵\n",
    "        for r, x in enumerate(arr):\n",
    "            # 也可以 while arr[st[-1]] > x，效率略高一点\n",
    "            while len(st) > 1 and arr[st[-1]] >= x:\n",
    "                i = st.pop()\n",
    "                ans += arr[i] * (i - st[-1]) * (r - i)  # 累加贡献\n",
    "            st.append(r)\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        # https://leetcode.cn/problems/sum-of-subarray-minimums/solutions/2544617/javapython3cgong-xian-fa-dan-diao-zhan-z-r92z/\n",
    "        MOD = 1000000007\n",
    "        n = len(arr)\n",
    "        right_less_idx = [n] * n   # 存储位置i之后首个小于nums[i]的位置，初始为n表示没有\n",
    "        st = []                  # 单调栈\n",
    "        \n",
    "        for i in range(n-1, -1, -1):\n",
    "            # 倒序遍历找到位置i之后的首个小于nums[i]的位置\n",
    "            while st and arr[i] <= arr[st[-1]]:\n",
    "                st.pop() # 弹出栈顶大于等于nums[i]的元素，一方面搜索比nums[i]小的元素位置，一方面淘汰被nums[i]取代的位置\n",
    "            if st:\n",
    "                right_less_idx[i] = st[-1] # 栈不为空，说明i之后存在小于nums[i]的位置\n",
    "            st.append(i)    # 当前位置入栈\n",
    "        \n",
    "        st.clear()  # 清空栈\n",
    "        res = 0     # 结果\n",
    "        \n",
    "        for i in range(n):\n",
    "            # 正序遍历找到位置i之前的首个小于等于nums[i]的位置，并且边寻找边计算nums[i]作为最小值的子数组数\n",
    "            while st and arr[i] < arr[st[-1]]:\n",
    "                st.pop() # 弹出栈顶大于等于nums[i]的元素，一方面搜索比nums[i]小的元素位置，一方面淘汰被nums[i]取代的位置\n",
    "            res += ((i - (st[-1] if st else -1)) * (right_less_idx[i] - i) * arr[i]) % MOD # (i, k)范围内可以构成的子数组的最小值都是arr[i]\n",
    "            res %= MOD\n",
    "            st.append(i) # 当前位置入栈\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        base = 10**9 + 7\n",
    "        stack, ans = [], 0\n",
    "        arr.append(0)\n",
    "        for i in range(len(arr)):\n",
    "            while stack and arr[i] <= arr[stack[-1]]:\n",
    "                k = stack.pop()\n",
    "                n = -1\n",
    "                if stack:\n",
    "                    n = stack[-1]\n",
    "                ans += (k - n) * arr[k] * (i - k)\n",
    "            stack.append(i)\n",
    "        return ans % base\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        '''n = len(arr)\n",
    "        left, stack = [-1]*n, []\n",
    "        for i, x in enumerate(arr):\n",
    "            while stack and arr[stack[-1]] >= x:\n",
    "                stack.pop()\n",
    "            if stack: left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        right, stack = [n]*n, []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stack and arr[stack[-1]] > arr[i]:\n",
    "                stack.pop()\n",
    "            if stack: right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            result += arr[i]*(i-left[i])*(right[i]-i)\n",
    "        return result % (10**9+7)'''\n",
    "\n",
    "        '''n = len(arr)\n",
    "        left, right, stack = [-1]*n , [n]*n, []\n",
    "        for i, x in enumerate(arr):\n",
    "            while stack and arr[stack[-1]] >= x:\n",
    "                right[stack.pop()] = i\n",
    "            if stack: left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            result += arr[i]*(i-left[i])*(right[i]-i)\n",
    "        return result % (10**9+7)'''\n",
    "\n",
    "        arr.append(-1)\n",
    "        result, stack = 0, [-1]\n",
    "        for r, x in enumerate(arr):\n",
    "            while len(stack) > 1 and arr[stack[-1]] >= x:\n",
    "                i = stack.pop()\n",
    "                result += arr[i] * (i-stack[-1]) * (r-i)\n",
    "            stack.append(r)\n",
    "        return result % (10**9+7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        # 找到左边第一个比当前元素小的元素的下标\n",
    "        for i, v in enumerate(arr):\n",
    "            j = i -1\n",
    "            while j >= 0 and arr[j] >= v:\n",
    "                j = left[j]\n",
    "            left[i] = j\n",
    "\n",
    "        # 找到右边第一个比当前元素小或等于的元素的下标\n",
    "        for i in range(n-1, -1, -1):\n",
    "            v = arr[i]\n",
    "            j = i + 1\n",
    "            while j < n and arr[j] > v:\n",
    "                j = right[j]\n",
    "            right[i] = j\n",
    "\n",
    "        mod = 10**9 + 7\n",
    "        return sum((i - left[i]) * (right[i] - i) * v for i, v in enumerate(arr)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        arr.append(-float('inf'))\n",
    "        n = len(arr)\n",
    "        mod = int(1e9+7)\n",
    "        for i in range(n):\n",
    "            while stack and arr[stack[-1]] > arr[i]:\n",
    "                ans += arr[stack[-1]] * ( stack[-1] + 1 if len(stack) == 1 else stack[-1] - stack[-2]) * (i - stack[-1])\n",
    "                ans %= mod\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        # ans = 0\n",
    "        # for i in range(len(arr)):\n",
    "        #     for j in range(i+1, len(arr)+1):\n",
    "        #         ans += min(arr[i:j])\n",
    "        #         print(arr[i:j])\n",
    "        #         print(max(arr[i:j]))\n",
    "        arr.append(-1)\n",
    "        ans, st = 0, [-1]  # 哨兵\n",
    "        for r, x in enumerate(arr):\n",
    "            # 也可以 while arr[st[-1]] > x，效率略高一点\n",
    "            while len(st) > 1 and arr[st[-1]] >= x:\n",
    "                i = st.pop()\n",
    "                ans += arr[i] * (i - st[-1]) * (r - i)  # 累加贡献\n",
    "            st.append(r)\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arrs: List[int]) -> int:\n",
    "        arrs.append(-1)\n",
    "        stk = [-1]\n",
    "        res = 0\n",
    "        for j in range(len(arrs)):\n",
    "            while arrs[stk[-1]] > arrs[j]:\n",
    "                i = stk.pop()\n",
    "                res += arrs[i] * (i - stk[-1]) * (j - i)\n",
    "            stk.append(j)\n",
    "        \n",
    "        return res % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        moder = 10 ** 9 + 7\n",
    "        arr.append(-1)\n",
    "        res, stk = 0, deque()\n",
    "        for i, x in enumerate(arr):\n",
    "            while stk and x <= arr[stk[-1]]:\n",
    "                top = stk.pop()\n",
    "                width = i - top\n",
    "                if stk:\n",
    "                    res = (res + (top - stk[-1]) * width * arr[top]) % moder\n",
    "                else:\n",
    "                    res = (res + (top + 1) * width * arr[top]) % moder\n",
    "            stk.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        st = []\n",
    "        for i, x in enumerate(arr):\n",
    "            while st and arr[st[-1]] >= x:\n",
    "                right[st.pop()] = i\n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        mod = int(1e9 + 7)\n",
    "        res = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            res += x * (i - left[i]) * (right[i] - i)\n",
    "            res %= mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left = [-1] * n\n",
    "        right = [n] * n\n",
    "        stk = []\n",
    "        for i, v in enumerate(arr):\n",
    "            while stk and arr[stk[-1]] >= v:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                left[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and arr[stk[-1]] > arr[i]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                right[i] = stk[-1]\n",
    "            stk.append(i)\n",
    "        mod = 10**9 + 7\n",
    "        return sum((i - left[i]) * (right[i] - i) * v for i, v in enumerate(arr)) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        left_min, right_min = [-1] * n, [n] * n\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and arr[i] < arr[stack[-1]]:         \n",
    "                left_min[stack.pop()] = i\n",
    "            right_min[i] = stack[-1] if stack else n\n",
    "            stack.append(i)\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += (i - left_min[i]) * (right_min[i] - i) * arr[i]\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 +7\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        monoStack = []\n",
    "        dp = [0] * n\n",
    "        ans = 0\n",
    "        for i,x in enumerate(arr):\n",
    "            while monoStack and arr[monoStack[-1]] > x:\n",
    "                monoStack.pop()\n",
    "            k = i - monoStack[-1] if monoStack else i+1\n",
    "            dp[i] = k * x + (dp[i-k] if monoStack else 0)\n",
    "            ans = (ans + dp[i]) % MOD\n",
    "            monoStack.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, A: List[int]) -> int:\n",
    "        ans = 0\n",
    "        A = [float('-inf')] + A + [float('-inf')]\n",
    "        stack = []\n",
    "        for i, a in enumerate(A):\n",
    "            while stack and A[stack[-1]] > a:\n",
    "                cur = stack.pop()\n",
    "                ans += A[cur] * (i - cur) * (cur - stack[-1])\n",
    "            stack.append(i)\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        monoStack = []\n",
    "        dp = [0] * n\n",
    "        ans = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            while monoStack and arr[monoStack[-1]] > x:\n",
    "                monoStack.pop()\n",
    "            k = i - monoStack[-1] if monoStack else i + 1\n",
    "            dp[i] = k * x + (dp[i - k] if monoStack else 0)\n",
    "            ans = (ans + dp[i]) % MOD\n",
    "            monoStack.append(i)\n",
    "        return ans\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        '''n = len(arr)\n",
    "        left, stack = [-1]*n, []\n",
    "        for i, x in enumerate(arr):\n",
    "            while stack and arr[stack[-1]] >= x:\n",
    "                stack.pop()\n",
    "            if stack: left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        right, stack = [n]*n, []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stack and arr[stack[-1]] > arr[i]:\n",
    "                stack.pop()\n",
    "            if stack: right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            result += arr[i]*(i-left[i])*(right[i]-i)\n",
    "        return result % (10**9+7)'''\n",
    "        n = len(arr)\n",
    "        left, right, stack = [-1]*n , [n]*n, []\n",
    "        for i, x in enumerate(arr):\n",
    "            while stack and arr[stack[-1]] >= x:\n",
    "                right[stack.pop()] = i\n",
    "            if stack: left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            result += arr[i]*(i-left[i])*(right[i]-i)\n",
    "        return result % (10**9+7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left = [-1] * n\n",
    "        st = []\n",
    "\n",
    "        for i in range(n):\n",
    "            # out\n",
    "            while st and arr[st[-1]] >= arr[i]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "            # in\n",
    "            st.append(i)\n",
    "        \n",
    "        right = [n] * n \n",
    "        st = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            # out \n",
    "            while st and arr[st[-1]] > arr[i]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                right[i] = st[-1]\n",
    "            # in\n",
    "            st.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += arr[i] * (i - left[i])* (right[i] - i)\n",
    "        \n",
    "        return ans % (10 ** 9 + 7)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        sum = 0\n",
    "        n = len(arr)\n",
    "\n",
    "        for i in range(n):\n",
    "            l = []\n",
    "            for j in arr:\n",
    "                l.append(j)\n",
    "                sum += min(l)\n",
    "            arr.pop(0)\n",
    "        \n",
    "        return sum\n",
    "'''\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left, right, st = [-1] * n, [n] * n, []\n",
    "        for i, x in enumerate(arr):\n",
    "            while st and arr[st[-1]] >= x:\n",
    "                right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for i, (x, l, r) in enumerate(zip(arr, left, right)):\n",
    "            ans += x * (i - l) * (r - i)\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        st = []\n",
    "        for i, x in enumerate(arr):\n",
    "            while st and arr[st[-1]] > x:\n",
    "                right[st.pop()] = i\n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        mod = int(1e9 + 7)\n",
    "        res = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            res += x * (i - left[i]) * (right[i] - i)\n",
    "            res %= mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mod = 1000000007\n",
    "        la = len(arr)\n",
    "        left = []\n",
    "        right = []\n",
    "        stack = []\n",
    "        for i in range(la):\n",
    "            while stack and arr[stack[-1]] > arr[i]:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                left.append(-1)\n",
    "            else:\n",
    "                left.append(stack[-1])\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(la):\n",
    "            while stack and arr[stack[-1]] >= arr[la - i - 1]:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                right.append(la)\n",
    "            else:\n",
    "                right.append(stack[-1])\n",
    "            stack.append(la - i - 1)\n",
    "        right.reverse()\n",
    "        for i in range(la):\n",
    "            print((i - left[i]) * (right[i] - i))\n",
    "            ans = (ans + arr[i] * (i - left[i]) * (right[i] - i)) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        stack = []\n",
    "        left = [0 for _ in range(n)]\n",
    "        right = [0 for _ in range(n)]\n",
    "\n",
    "        for i, x in enumerate(arr):\n",
    "            while stack and arr[stack[-1]] > x:\n",
    "                stack.pop(-1)\n",
    "            left[i] = i - (stack[-1] if stack else -1)\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and arr[i] <= arr[stack[-1]]:\n",
    "                stack.pop()\n",
    "            right[i] = (stack[-1] if stack else n) - i\n",
    "            stack.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for l, r, x in zip(left, right, arr):\n",
    "            ans = (ans + l*r*x)%(10 ** 9 + 7)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        monoStack = []\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            while monoStack and x <= arr[monoStack[-1]]:\n",
    "                monoStack.pop()\n",
    "            left[i] = i - (monoStack[-1] if monoStack else -1)\n",
    "            monoStack.append(i)\n",
    "        monoStack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while monoStack and arr[i] < arr[monoStack[-1]]:\n",
    "                monoStack.pop()\n",
    "            right[i] = (monoStack[-1] if monoStack else n) - i\n",
    "            monoStack.append(i)\n",
    "        ans = 0\n",
    "        for l, r, x in zip(left, right, arr):\n",
    "            ans = (ans + l * r * x) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        stack = []\n",
    "        left = [0 for _ in range(n)]\n",
    "        right = [0 for _ in range(n)]\n",
    "\n",
    "        for i, x in enumerate(arr):\n",
    "            while stack and arr[stack[-1]] >= x:\n",
    "                stack.pop(-1)\n",
    "            left[i] = i - (stack[-1] if stack else -1)\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and arr[i] < arr[stack[-1]]:\n",
    "                stack.pop()\n",
    "            right[i] = (stack[-1] if stack else n) - i\n",
    "            stack.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for l, r, x in zip(left, right, arr):\n",
    "            ans = (ans + l*r*x)%(10 ** 9 + 7)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(arr)\n",
    "        r, stk = [n] * n, []\n",
    "        for i, x in enumerate(arr):\n",
    "            while stk and x <= arr[stk[-1]]:\n",
    "                r[stk.pop()] = i\n",
    "            stk.append(i)\n",
    "\n",
    "        l, stk = [-1] * n, []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and arr[i] < arr[stk[-1]] :\n",
    "                l[stk.pop()] = i\n",
    "            stk.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for i, (x, lb, rb) in enumerate(zip(arr, l, r)):\n",
    "            ans += x * (rb - i) * (i - lb)\n",
    "        return ans % MOD\n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        monoStack = []\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            while monoStack and x <= arr[monoStack[-1]]:\n",
    "                monoStack.pop()\n",
    "            left[i] = i - (monoStack[-1] if monoStack else -1)\n",
    "            monoStack.append(i)\n",
    "        monoStack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while monoStack and arr[i] < arr[monoStack[-1]]:\n",
    "                monoStack.pop()\n",
    "            right[i] = (monoStack[-1] if monoStack else n) - i\n",
    "            monoStack.append(i)\n",
    "        ans = 0\n",
    "        for l, r, x in zip(left, right, arr):\n",
    "            ans = (ans + l * r * x) % MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        st = []\n",
    "        for i, x in enumerate(arr):\n",
    "            while st and arr[st[-1]] > x:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        st = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while st and arr[st[-1]] >= arr[i]:\n",
    "                st.pop()\n",
    "            if st:\n",
    "                right[i] = st[-1]\n",
    "            st.append(i)\n",
    "        mod = int(1e9 + 7)\n",
    "        res = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            res += x * (i - left[i]) * (right[i] - i)\n",
    "            res %= mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        monoStack = []\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            while monoStack and x <= arr[monoStack[-1]]:\n",
    "                monoStack.pop()\n",
    "            left[i] = i - (monoStack[-1] if monoStack else -1)\n",
    "            monoStack.append(i)\n",
    "        monoStack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while monoStack and arr[i] < arr[monoStack[-1]]:\n",
    "                monoStack.pop()\n",
    "            right[i] = (monoStack[-1] if monoStack else n) - i\n",
    "            monoStack.append(i)\n",
    "        ans = 0\n",
    "        for l, r, x in zip(left, right, arr):\n",
    "            ans = (ans + l * r * x) % MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        len_arr = len(arr)\n",
    "        left = [0] * len_arr\n",
    "        right = [0] * len_arr\n",
    "        small_left = []\n",
    "        for i, num in enumerate(arr):\n",
    "            while small_left and num <= arr[small_left[-1]]:\n",
    "                small_left.pop()\n",
    "            left[i] = i - (small_left[-1] if small_left else -1)\n",
    "            small_left.append(i)\n",
    "        \n",
    "        small_right = []\n",
    "        for i in range(len_arr-1, -1, -1):\n",
    "            while small_right and arr[i] < arr[small_right[-1]]:\n",
    "                small_right.pop()\n",
    "            right[i] = (small_right[-1] if small_right else len_arr) - i\n",
    "            small_right.append(i)\n",
    "\n",
    "        res = 0\n",
    "        mod_num = 10**9+7\n",
    "        for l, r, num in zip(left, right, arr):\n",
    "            res = (res + l * r * num) % mod_num\n",
    "        return res\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left = [-1]*n\n",
    "        right = [n]*n\n",
    "        st = []\n",
    "        for i,j in enumerate(arr):\n",
    "            while st and j<arr[st[-1]]:\n",
    "                st.pop()\n",
    "            left[i] = st[-1] if st else -1\n",
    "            st.append(i)\n",
    "        st = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while st and arr[i]<=arr[st[-1]]:\n",
    "                st.pop()\n",
    "            right[i] = st[-1] if st else n\n",
    "            st.append(i)\n",
    "            \n",
    "            \n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += (i-left[i])*(right[i]-i)*arr[i]\n",
    "            ans %= 10**9+7\n",
    "        print(left,right)\n",
    "        return ans\n",
    "\n",
    "# 71"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        left, right = [0]*len(arr), [0]*len(arr)\n",
    "        \n",
    "        stack = list()\n",
    "        for i in range(len(arr)):\n",
    "            while stack and arr[i] <= arr[stack[-1]]:\n",
    "                stack.pop()\n",
    "            left[i] = stack[-1] if stack else -1\n",
    "            stack.append(i)\n",
    "\n",
    "        \n",
    "        stack = list()\n",
    "        for i in range(len(arr) - 1, -1, -1):\n",
    "            while stack and arr[i] < arr[stack[-1]]:\n",
    "                stack.pop()\n",
    "            right[i] = stack[-1] if stack else len(arr)\n",
    "            stack.append(i)\n",
    "        \n",
    "        result = 0\n",
    "        for i in range(len(arr)):\n",
    "            result = (result + arr[i] * (i - left[i]) * (right[i] - i)) % MOD\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        res = 0\n",
    "        left, right = [-1] * len(arr), [len(arr)] * len(arr)\n",
    "        stack = []\n",
    "        for i in range(len(arr)):\n",
    "            while stack and arr[stack[-1]] >= arr[i]:\n",
    "                idx = stack.pop()\n",
    "                right[idx] = i\n",
    "            stack.append(i)\n",
    "        stack.clear()\n",
    "        for i in range(len(arr) - 1, -1, -1):\n",
    "            while stack and arr[stack[-1]] > arr[i]:\n",
    "                idx = stack.pop()\n",
    "                left[idx] = i\n",
    "            stack.append(i)\n",
    "        stack.clear()\n",
    "        for i in range(len(arr)):\n",
    "            res += (i-left[i]) * (right[i]-i)*arr[i]\n",
    "        return res % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left = [1]*n\n",
    "        right = [1]*n\n",
    "        s = []\n",
    "        for i in range(n):\n",
    "            while s and arr[i] <= arr[s[-1]]:\n",
    "                s.pop()\n",
    "            left[i] = i-s[-1] if s else i+1\n",
    "            s.append(i)\n",
    "        s = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while s and arr[i] < arr[s[-1]]:\n",
    "                s.pop()\n",
    "            right[i] = s[-1]-i if s else n-i\n",
    "            s.append(i)\n",
    "        res, mod = 0, 10**9+7\n",
    "        print(left)\n",
    "        print(right)\n",
    "        for i in range(n):\n",
    "            res = (res+arr[i]*left[i]*right[i])%mod\n",
    "        return res\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        moder = 10 ** 9 + 7\n",
    "        arr.append(-1)\n",
    "        res, stk = 0, deque()\n",
    "        tmp = []\n",
    "        for i, x in enumerate(arr):\n",
    "            while stk and x <= arr[stk[-1]]:\n",
    "                top = stk.pop()\n",
    "                width = i - top\n",
    "                if stk:\n",
    "                    tmp.append((top - stk[-1]) * width * arr[top])\n",
    "                    res = (res + (top - stk[-1]) * width * arr[top]) % moder\n",
    "                else:\n",
    "                    tmp.append((top + 1) * width * arr[top])\n",
    "                    res = (res + (top + 1) * width * arr[top]) % moder\n",
    "            stk.append(i)\n",
    "        print(tmp)\n",
    "        return res\n",
    "\n",
    "        # 2 2 3\n",
    "        # 0 4 1 2 3 2 1 1\n",
    "        # 0   1 2 2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(arr)\n",
    "        left, right = [0] * n, [0] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            if not stack or arr[stack[-1]] < arr[i]:\n",
    "                stack.append(i)\n",
    "                left[i] = 1\n",
    "            else:\n",
    "                tmp = 0\n",
    "                while stack and arr[stack[-1]] >= arr[i]:\n",
    "                    tmp += left[stack[-1]]\n",
    "                    stack.pop()\n",
    "                stack.append(i)\n",
    "                left[i] = 1 + tmp\n",
    "        stack.clear()\n",
    "        for j in range(n - 1, -1, -1):\n",
    "            if not stack or arr[stack[-1]] <= arr[j]:\n",
    "                stack.append(j)\n",
    "                right[j] = 1\n",
    "            else:\n",
    "                tmp = 0\n",
    "                while stack and arr[stack[-1]] > arr[j]:\n",
    "                    tmp += right[stack[-1]]\n",
    "                    stack.pop()\n",
    "                stack.append(j)\n",
    "                right[j] = 1 + tmp\n",
    "        for k in range(n):\n",
    "            res += left[k] * right[k] * arr[k]\n",
    "        print(left, right, arr)\n",
    "        return res % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        rb = [0] * n\n",
    "        ans = 0\n",
    "\n",
    "        st = [(-inf, n)]\n",
    "        _append = st.append\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            num = arr[i]\n",
    "            while num < st[-1][0]:\n",
    "                st.pop()\n",
    "            \n",
    "            rb[i] = st[-1][1] - i\n",
    "            _append((num, i))\n",
    "        \n",
    "        st.clear()\n",
    "        _append((-inf, -1))\n",
    "\n",
    "        for i, num in enumerate(arr):\n",
    "            while num <= st[-1][0]:\n",
    "                st.pop()\n",
    "            \n",
    "            ans = (ans + num * (i - st[-1][1]) * rb[i]) % MOD\n",
    "            _append((num, i))\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        next_left_lesser = [-1 for _ in range(len(arr))]\n",
    "        next_right_lesser = [len(arr) for _ in range(len(arr))]\n",
    "\n",
    "        stack = []\n",
    "        for i in range(len(arr)):\n",
    "            if not stack:\n",
    "                stack.append(i)\n",
    "                continue\n",
    "            while stack and arr[stack[-1]] >= arr[i]:\n",
    "                next_right_lesser[stack.pop()] = i\n",
    "            stack.append(i)\n",
    "        \n",
    "        stack = []\n",
    "        for i in range(len(arr) - 1, -1, -1):\n",
    "            if not stack:\n",
    "                stack.append(i)\n",
    "                continue\n",
    "            while stack and arr[stack[-1]] > arr[i]:\n",
    "                next_left_lesser[stack.pop()] = i\n",
    "            stack.append(i)\n",
    "        # print(next_left_lesser)\n",
    "        # print(next_right_lesser)\n",
    "\n",
    "        ret = 0\n",
    "        for i in range(len(arr)):\n",
    "            ret += arr[i] * (i - next_left_lesser[i]) * (next_right_lesser[i] - i)\n",
    "        return ret % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        postMin[i]: 记录i元素之后第一个小于等于它的元素下标 x\n",
    "        preMin[i]: 记录i元素之前第一个比它小的元素下标 y\n",
    "        那么可以以i元素作为最小值的子数组数量为(x-i) + (i-y)\n",
    "        \"\"\"\n",
    "        n = len(arr)\n",
    "        left = [-1] * n  # left[i]: i元数左侧最近的比它小的元素下标\n",
    "        stk = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stk and arr[i] < arr[stk[-1]]:\n",
    "                left[stk.pop()] = i\n",
    "            stk.append(i)\n",
    "        print(left)\n",
    "\n",
    "        stk = []\n",
    "        right = [n] * n\n",
    "        for i in range(n):\n",
    "            while stk and arr[i] <= arr[stk[-1]]:\n",
    "                right[stk.pop()] = i\n",
    "            stk.append(i)\n",
    "        print(right)\n",
    "\n",
    "        ans = 0\n",
    "        for i, (x, l, r) in enumerate(zip(arr, left, right)):\n",
    "            ans += x * (i-l) * (r-i)\n",
    "        return ans % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        c=len(arr)\n",
    "        xx=[0]*c\n",
    "        yy=[0]*c \n",
    "        ff=[]\n",
    "        f=-1\n",
    "        md=1000000007\n",
    "\n",
    "        def dwcx(aa,ff):\n",
    "            f=-1\n",
    "            for i in range(c):\n",
    "                if f<0 or ff[f][1]<=arr[i]: \n",
    "                    ff.append([i,arr[i]])\n",
    "                    f+=1\n",
    "                else:\n",
    "                    while f>=0 and ff[f][1]>arr[i]:\n",
    "                        kk=ff.pop()\n",
    "                        f-=1\n",
    "                        xx[kk[0]]=i-kk[0]-1\n",
    "                    ff.append([i,arr[i]])\n",
    "                    f+=1\n",
    "\n",
    "            while f>=0:\n",
    "                kk=ff.pop()\n",
    "                f-=1\n",
    "                xx[kk[0]]=c-kk[0]-1\n",
    "        \n",
    "\n",
    "        def dwfcx(aa):\n",
    "            f=-1\n",
    "            ff=[]\n",
    "            for i in range(c-1,-1,-1):\n",
    "                if f<0 or ff[f][1]<arr[i]: \n",
    "                    ff.append([i,arr[i]])\n",
    "                    f+=1\n",
    "                else:\n",
    "                    while f>=0 and ff[f][1]>=arr[i]:\n",
    "                        kk=ff.pop()\n",
    "                        f-=1\n",
    "                        aa[kk[0]]=kk[0]-i-1\n",
    "                    ff.append([i,arr[i]])\n",
    "                    f+=1\n",
    "        \n",
    "            while f>=0:\n",
    "                kk=ff.pop()\n",
    "                f-=1\n",
    "                aa[kk[0]]=kk[0]\n",
    "\n",
    "\n",
    "        dwcx(xx,ff)\n",
    "       \n",
    "        dwfcx(yy)\n",
    "   \n",
    "        ret=0   \n",
    "        for i in range(c):\n",
    "            ret+=(xx[i]+1)*(yy[i]+1)*arr[i]\n",
    "            ret%=md\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        mod=int(1e9+7)\n",
    "        v=[]\n",
    "        r=[]\n",
    "        l=[]\n",
    "        for i in range(n):\n",
    "            #print(arr[i],end=\"op\")\n",
    "            l.append(-1)\n",
    "            r.append(n)\n",
    "\n",
    "        for i in range(n):\n",
    "            #print(i,\": \")\n",
    "\n",
    "            while len(v) and arr[v[len(v)-1]]>arr[i]:\n",
    "                #print(v[len(v)-1],i,\"oppopp\")\n",
    "                r[v[len(v)-1]]=i\n",
    "                v.pop()\n",
    "            v.append(i)\n",
    "        v.clear()\n",
    "\n",
    "\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while len(v) and arr[i]<=arr[v[len(v)-1]]:\n",
    "                l[v[len(v)-1]]=i\n",
    "                v.pop()\n",
    "            v.append(i)\n",
    "            \n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            res+=arr[i]*(i-l[i])*(r[i]-i)\n",
    "            print((i-l[i]),(r[i]-i))\n",
    "\n",
    "        return res%mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        st = [[arr[0],1]]\n",
    "        f = [0]*n\n",
    "        f[0] = arr[0]\n",
    "        for i in range(1,n):\n",
    "            if arr[i]>st[-1][0]:\n",
    "                st.append([arr[i],1])\n",
    "                f[i] = (f[i-1]+arr[i]) % (10**9+7)\n",
    "            else:\n",
    "                tmp = 1\n",
    "                while(len(st)>0 and st[-1][0]>=arr[i]):\n",
    "                    tmp+=st[-1][1]\n",
    "                    st.pop(-1)\n",
    "                st.append([arr[i],tmp])\n",
    "                f[i] = (f[i-tmp]+arr[i]*tmp) % (10**9+7)\n",
    "        r = 0\n",
    "        for i in f:\n",
    "            r = (r+i) % (10**9+7)\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        s = []\n",
    "        cnt = [0] * n\n",
    "        for i in range(n):\n",
    "            if len(s) == 0 or s[len(s) - 1][0] < arr[i]:\n",
    "                s.append([arr[i], i])\n",
    "            else:\n",
    "                while len(s) != 0 and s[len(s) - 1][0] >= arr[i]:\n",
    "                    cnt[s[len(s) - 1][1]] += i - s[len(s) - 1][1]\n",
    "                    s.pop()\n",
    "                s.append([arr[i], i])\n",
    "        while len(s):\n",
    "            cnt[s[len(s) - 1][1]] += n - s[len(s) -1][1]\n",
    "            s.pop()\n",
    "        s = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if len(s) == 0 or s[len(s) - 1][0] <= arr[i]:\n",
    "                s.append([arr[i], i])\n",
    "            else:\n",
    "                while len(s) != 0 and s[len(s) - 1][0] > arr[i]:\n",
    "                    cnt[s[len(s) - 1][1]] *= s[len(s) - 1][1] - i\n",
    "                    s.pop()\n",
    "                s.append([arr[i], i])\n",
    "        while len(s):\n",
    "            cnt[s[len(s) - 1][1]] *= s[len(s) - 1][1] + 1\n",
    "            s.pop()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += cnt[i] * arr[i]\n",
    "        return ans % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        M = 1000000007\n",
    "        r, l = [0] * n, [0] * n\n",
    "        q = []\n",
    "        for i, a in enumerate(arr):\n",
    "            while q and q[-1][0] > a:\n",
    "                q.pop()\n",
    "            if not q:\n",
    "                l[i] = -1\n",
    "            else:\n",
    "                l[i] = q[-1][1]\n",
    "            q.append((a, i))\n",
    "        q = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while q and q[-1][0] >= arr[i]:\n",
    "                q.pop()\n",
    "            if not q:\n",
    "                r[i] = n\n",
    "            else:\n",
    "                r[i] = q[-1][1]\n",
    "            q.append((arr[i], i))\n",
    "        \n",
    "        for i in range(n):\n",
    "            ans += ((arr[i] * (i - l[i]) * (r[i] - i)) % M)\n",
    "        return ans % M\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        # arr[i]用了几次取决于在多少个subarray中他是最小的\n",
    "        from collections import deque\n",
    "        res = 0\n",
    "        length = len(arr)\n",
    "        # 单调栈 FILO\n",
    "        stack_right = []\n",
    "        res_right = [-1] * length\n",
    "        stack_left = []\n",
    "        res_left = [-1] * length\n",
    "        for i in range(length):\n",
    "            # 找到往右第一个比栈顶元素index<的,剩下的都比他大=\n",
    "            # 第i个比栈顶元素大\n",
    "            while stack_right and arr[i] < arr[stack_right[-1]]:\n",
    "                # 弹出栈顶元素\n",
    "                top = stack_right.pop()\n",
    "                #\n",
    "                res_right[top] = i\n",
    "            stack_right.append(i)\n",
    "\n",
    "            # 找到往左第一个比栈顶元素index<=的,剩下的都比他大\n",
    "            # 第length-1-i个比栈顶元素大\n",
    "            while stack_left and arr[length-1-i] <= arr[stack_left[-1]]:\n",
    "                top = stack_left.pop()\n",
    "                res_left[top] = length-1-i\n",
    "            stack_left.append(length-1-i)\n",
    "\n",
    "        # print(res_left)\n",
    "        # print(res_right)\n",
    "\n",
    "        # 往左都比它大才行\n",
    "        # 往右大于等于\n",
    "\n",
    "        for i in range(length):\n",
    "            # arr[i]用到的次数: 和左边组成，和右边组成，假设arr[i]是最小的\n",
    "            n_left, n_right = i + 1, length - i\n",
    "            # 左边有比arr[i]小\n",
    "            if res_left != -1:\n",
    "                n_left -= (res_left[i] + 1)\n",
    "            #右边有比arr[i]小的\n",
    "            if res_right[i] != -1:\n",
    "                n_right -= (length - res_right[i])\n",
    "\n",
    "            # print(n_left,n_right,arr[i])\n",
    "            res += (n_left * n_right) * arr[i]\n",
    "            res %= (10**9 + 7)\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n, mi, ans = len(arr), min(arr), 0\n",
    "        l, r, lstl, lstr = -1, n, [-1], [n]\n",
    "        for i in range(1, n):\n",
    "            if    arr[i] == mi               : l  = -1\n",
    "            elif  arr[i] >  arr[i - 1]       : l  = i - 1\n",
    "            while l >= 0 and arr[l] >= arr[i]: l -= 1\n",
    "            lstl.append(l)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if    arr[i] >= arr[i + 1]       : r  = i + 1\n",
    "            while r <  n and arr[r] >  arr[i]: r += 1\n",
    "            lstr.append(r)\n",
    "        lstr = lstr[::-1]\n",
    "        for i in range(n): ans = (ans + arr[i] * (lstr[i] - i) * (i - lstl[i])) % 1000000007\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        # 单调栈\n",
    "        # 往左找第一个比当前数小的数为左边界 往右找第一个比当前数小的数为右边界\n",
    "        # 根据左右边界可以获得该数的辐射范围\n",
    "        stack = []\n",
    "        left = [-1] * len(arr)\n",
    "        right = [-1] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            if not stack:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while stack and arr[i] < arr[stack[-1]]:\n",
    "                    right[stack.pop()] = i\n",
    "                stack.append(i)\n",
    "        right = [len(arr) if right[i] == -1 else right[i] for i in range(len(arr))]\n",
    "        stack = []\n",
    "\n",
    "        for i in range(len(arr)-1, -1, -1):\n",
    "            if not stack:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while stack and arr[i] <= arr[stack[-1]]:\n",
    "                    left[stack.pop()] = i\n",
    "                stack.append(i)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(len(arr)):\n",
    "            res += arr[i] * (i - left[i]) * (right[i] - i) \n",
    "      \n",
    "        return res % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        stack = []\n",
    "        left = [0] * n\n",
    "        right = [0] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            while stack and arr[stack[-1]] > arr[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1] + 1\n",
    "            else:\n",
    "                left[i] = 0\n",
    "            stack.append(i)\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and arr[stack[-1]] >= arr[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1]\n",
    "            else:\n",
    "                right[i] = n\n",
    "            stack.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += arr[i] * (i - left[i] + 1) * (right[i] - i)\n",
    "            ans %= MOD\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        stack = [(-1,-1)]\n",
    "        pre = []\n",
    "        n = len(arr)\n",
    "        for i,num in enumerate(arr):\n",
    "            while stack[-1][1] >= num:\n",
    "                stack.pop()\n",
    "            pre.append(stack[-1][0])\n",
    "            stack.append((i,num))\n",
    "        stack = [(n,-1)]\n",
    "        suf = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            num = arr[i]\n",
    "            while stack[-1][1] > num:\n",
    "                stack.pop()\n",
    "            suf.append(stack[-1][0])\n",
    "            stack.append((i,num))\n",
    "        suf = suf[::-1]\n",
    "        res = 0\n",
    "        MOD = 10**9+7\n",
    "        for i in range(n):\n",
    "            res = (res + arr[i]*(suf[i]-i)*(i-pre[i]))%MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "            MOD = 10**9 + 7\n",
    "            n = len(arr)\n",
    "            stack = []\n",
    "            left = [0] * n\n",
    "            right = [0] * n\n",
    "            result = 0\n",
    "\n",
    "            for i in range(n):\n",
    "                while stack and arr[stack[-1]] > arr[i]:\n",
    "                    stack.pop()\n",
    "                if stack:\n",
    "                    left[i] = stack[-1] + 1\n",
    "                else:\n",
    "                    left[i] = 0\n",
    "                stack.append(i)\n",
    "\n",
    "            stack = []\n",
    "\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                while stack and arr[stack[-1]] >= arr[i]:\n",
    "                    stack.pop()\n",
    "                if stack:\n",
    "                    right[i] = stack[-1]\n",
    "                else:\n",
    "                    right[i] = n\n",
    "                stack.append(i)\n",
    "\n",
    "            for i in range(n):\n",
    "                result += arr[i] * (i - left[i] + 1) * (right[i] - i)  # 累加每个子数组的最小值\n",
    "                result %= MOD\n",
    "\n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr) -> int:\n",
    "        ans = 0\n",
    "        MOD = 1000000007\n",
    "        if len(arr) == 1:\n",
    "            return arr[0] % MOD\n",
    "        right = [0 for _ in range(len(arr))]\n",
    "        left = [0 for _ in range(len(arr))]\n",
    "        stack = []\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            if len(stack) == 0:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while(len(stack) != 0 and arr[i] < arr[stack[-1]]):\n",
    "                    right[stack.pop()] = i - 1\n",
    "                stack.append(i)\n",
    "        while(len(stack) != 0):\n",
    "            right[stack.pop()] = len(arr) - 1\n",
    "\n",
    "        for i in range(len(arr) - 1, -1, -1):\n",
    "            if len(stack) == 0:\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                while(len(stack) != 0 and arr[i] <= arr[stack[-1]]):\n",
    "                    left[stack.pop()] = i + 1\n",
    "                stack.append(i)\n",
    "        while(len(stack) != 0):\n",
    "            left[stack.pop()] = 0\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            ans += (i - left[i] + 1) * (right[i] - i + 1) * arr[i]\n",
    "        ans %= MOD\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        result = 0\n",
    "        stack = []\n",
    "        L = [0] * len(arr)\n",
    "        R = [0] * len(arr)\n",
    "        for i in range(len(arr)):\n",
    "            while stack and arr[stack[-1]] > arr[i]:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                L[i] = 0\n",
    "            else:\n",
    "                L[i] = stack[-1] +1\n",
    "            stack.append(i)  \n",
    "\n",
    "        stack = []\n",
    "        for i in range(len(arr)-1, -1, -1):\n",
    "            while stack and arr[stack[-1]] >= arr[i]:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                R[i] = len(arr) - 1\n",
    "            else:\n",
    "                R[i] = stack[-1] - 1\n",
    "            stack.append(i)\n",
    "        \n",
    "        for i in range(len(arr)):\n",
    "            result += arr[i] * (i - L[i] + 1) * (R[i] - i + 1)\n",
    "            result %= 1000000007\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "     def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        # arr[i]用了几次取决于在多少个subarray中他是最小的\n",
    "        from collections import deque\n",
    "        res = 0\n",
    "        length = len(arr)\n",
    "        # 单调栈 FILO\n",
    "        stack_right = []\n",
    "        res_right = [-1] * length\n",
    "        stack_left = []\n",
    "        res_left = [-1] * length\n",
    "        for i in range(length):\n",
    "            # 找到往右第一个比栈顶元素index<的,剩下的都比他大=\n",
    "            # 第i个比栈顶元素大\n",
    "            while stack_right and arr[i] < arr[stack_right[-1]]:\n",
    "                # 弹出栈顶元素\n",
    "                top = stack_right.pop()\n",
    "                #\n",
    "                res_right[top] = i\n",
    "            stack_right.append(i)\n",
    "\n",
    "            # 找到往左第一个比栈顶元素index<=的,剩下的都比他大\n",
    "            # 第length-1-i个比栈顶元素大\n",
    "            while stack_left and arr[length-1-i] <= arr[stack_left[-1]]:\n",
    "                top = stack_left.pop()\n",
    "                res_left[top] = length-1-i\n",
    "            stack_left.append(length-1-i)\n",
    "\n",
    "        # print(res_left)\n",
    "        # print(res_right)\n",
    "\n",
    "        # 往左都比它大才行\n",
    "        # 往右大于等于\n",
    "\n",
    "        for i in range(length):\n",
    "            # arr[i]用到的次数: 和左边组成，和右边组成，假设arr[i]是最小的\n",
    "            n_left, n_right = i + 1, length - i\n",
    "            # 左边有比arr[i]小\n",
    "            if res_left != -1:\n",
    "                n_left -= (res_left[i] + 1)\n",
    "            #右边有比arr[i]小的\n",
    "            if res_right[i] != -1:\n",
    "                n_right -= (length - res_right[i])\n",
    "\n",
    "            # print(n_left,n_right,arr[i])\n",
    "            res += (n_left * n_right) * arr[i]\n",
    "            res %= (10**9 + 7)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: list) -> int:\n",
    "        n = len(arr)\n",
    "        left, right = [0] * n, [0] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and arr[stack[-1]] > arr[i]:\n",
    "                stack.pop()\n",
    "            left[i] = stack[-1] + 1 if stack else 0\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while stack and arr[stack[-1]] >= arr[i]:\n",
    "                stack.pop()\n",
    "            right[i] = stack[-1] - 1 if stack else n-1\n",
    "            stack.append(i)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res = (arr[i] * ((right[i] - i + 1) * (i - left[i] + 1))) % MOD + res % MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        MOD = 10 ** 9  + 7\n",
    "        def help(arr, equal=False):\n",
    "            asc_st = []\n",
    "            j = -1\n",
    "            starts = []\n",
    "            for i, v in enumerate(arr):\n",
    "                if equal:\n",
    "                    while asc_st and asc_st[-1][1] >= v:\n",
    "                        asc_st.pop(-1)\n",
    "                else:\n",
    "                    while asc_st and asc_st[-1][1] > v:\n",
    "                        asc_st.pop(-1)\n",
    "                if asc_st:\n",
    "                    starts.append(asc_st[-1][0])\n",
    "                else:\n",
    "                    starts.append(-1)\n",
    "                asc_st.append((i, v))\n",
    "            return starts\n",
    "        starts = help(arr)\n",
    "        ends = help(reversed(arr), True)\n",
    "        ends = [len(arr) - x - 1 for x in reversed(ends)]\n",
    "        ans = 0\n",
    "        for k, (i, j, v) in enumerate(zip(starts, ends, arr)):\n",
    "            ans += (k - i) * (j - k) * v % MOD\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        res = 0\n",
    "        mod = 1e9+7\n",
    "        # for i, v in enumerate(arr):\n",
    "        #     tmp = v\n",
    "        #     for j, t in enumerate(arr[i:], start=i):\n",
    "        #         tmp = min(tmp, t)\n",
    "        #         res += tmp\n",
    "        n = len(arr)\n",
    "        stack = deque([(-float(\"inf\"), -1)])\n",
    "        left, right = [None,]*n, [None,]*n\n",
    "        for i in range(n):\n",
    "            while stack[-1][0] >= arr[i]:\n",
    "                stack.pop()\n",
    "            left[i] = i-stack[-1][1]\n",
    "            stack.append((arr[i], i))\n",
    "        stack = deque([(-float(\"inf\"), n)])\n",
    "        for j in range(n-1, -1, -1):\n",
    "            while stack[-1][0] > arr[j]:\n",
    "                stack.pop()\n",
    "            right[j] = stack[-1][1]-j\n",
    "            stack.append((arr[j], j))\n",
    "        \n",
    "        print(left, right)\n",
    "        for i in range(n):\n",
    "            res += left[i]*right[i]*arr[i]\n",
    "            res %= mod\n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 100_000_000_7\n",
    "class Solution:\n",
    "    def traverse(self, arr: List[int], eq = False) -> List[int]:\n",
    "        n = len(arr)\n",
    "        st = []\n",
    "        dp = [0] * n\n",
    "        for i, num in enumerate(arr):\n",
    "            while len(st) > 0:\n",
    "                top = st[-1]\n",
    "                if eq:\n",
    "                    if top[0] >= num:\n",
    "                        dp[top[1]] = i - top[1]\n",
    "                        st.pop()\n",
    "                    else: break\n",
    "                else:\n",
    "                    if top[0] > num:\n",
    "                        dp[top[1]] = i - top[1]\n",
    "                        st.pop()\n",
    "                    else: break  \n",
    "            st.append((num, i))\n",
    "        while len(st) > 0:\n",
    "            top = st[-1]\n",
    "            dp[top[1]] = n - top[1]\n",
    "            st.pop()\n",
    "        return dp\n",
    "\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans1 = self.traverse(arr, True)\n",
    "        ans2 = self.traverse(list(reversed(arr)))\n",
    "        print(ans1)\n",
    "        print(ans2)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = ((ans1[i] * ans2[n - 1 - i] * arr[i]) % mod + ans % mod) % mod\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: list[int]) -> int:\n",
    "        stk, left, right, n = [], [], [], len(arr)\n",
    "        for i in range(n):\n",
    "            while len(stk) > 0 and stk[-1][0] >= arr[i]:\n",
    "                stk.pop()\n",
    "            if len(stk) == 0:\n",
    "                left.append(-1)\n",
    "            else:\n",
    "                left.append(stk[-1][1])\n",
    "            stk.append((arr[i], i))\n",
    "        stk = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while len(stk) > 0 and stk[-1][0] > arr[i]:\n",
    "                stk.pop()\n",
    "            if len(stk) == 0:\n",
    "                right.append(n)\n",
    "            else:\n",
    "                right.append(stk[-1][1])\n",
    "            stk.append((arr[i], i))\n",
    "        res = 0\n",
    "        print(left, right)\n",
    "        for i in range(n):\n",
    "            res = int((res + arr[i] * (i - left[i]) * (right[n-1-i] - i)) % (1e9+7))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        stack,n = [0],len(arr)\n",
    "        ans = arr[0]\n",
    "        pre = [[] for _ in range(n)]\n",
    "        pre[0] = arr[0]\n",
    "        for i in range(1,n):\n",
    "            temp = 0\n",
    "            while stack and arr[stack[-1]]>arr[i]: \n",
    "                stack.pop()\n",
    "            if stack: \n",
    "                temp += pre[stack[-1]]\n",
    "            temp += ((i-stack[-1]) if stack else i+1)*arr[i]\n",
    "            ans+=temp\n",
    "            stack.append(i)\n",
    "            pre[i]=temp\n",
    "        print(pre)\n",
    "        return int(ans%(1e9+7))\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        cnt = [[-1,n] for _ in range(n)]\n",
    "        st = [[0,-1]]\n",
    "        for idx,i in enumerate(arr):\n",
    "            while st[-1][0]>=i:\n",
    "                val,ix = st.pop()\n",
    "                cnt[ix][1] = idx\n",
    "            cnt[idx][0] = st[-1][1]\n",
    "            st.append([i,idx])\n",
    "        ans = 0\n",
    "        mod = 10**9+7\n",
    "        for i in range(n):\n",
    "            ans+=arr[i]*(i-cnt[i][0])*(cnt[i][1]-i)\n",
    "            ans %=mod \n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        stack = [[-1, -float('inf')]]\n",
    "        arrRight = [len(arr) - 1] * len(arr)\n",
    "        arrLeft = [0] * len(arr)\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            item = arr[i]\n",
    "            while item <= stack[-1][1]:\n",
    "                arrRight[stack[-1][0]] = i - 1\n",
    "                stack.pop()\n",
    "            stack.append([i,item])\n",
    "\n",
    "        stack = [[-1,-float('inf')]]\n",
    "        for i in range(len(arr) - 1 ,-1, -1):\n",
    "            item = arr[i]\n",
    "            while item < stack[-1][1]:\n",
    "                arrLeft[stack[-1][0]] = i + 1\n",
    "                stack.pop()\n",
    "            stack.append([i, item])\n",
    "        \n",
    "        \n",
    "        res = 0\n",
    "        for i in range(len(arr)):\n",
    "            res += arr[i] * (i  - arrLeft[i] + 1) * (arrRight[i] - i + 1)\n",
    "        return int(res % (1e9 + 7))\n",
    "\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        pre=[0]*len(arr)\n",
    "        lat=[0]*len(arr)\n",
    "        queue=[]\n",
    "        for i in range(len(arr)):\n",
    "            while queue and queue[-1][0]>=arr[i]:\n",
    "                queue.pop()\n",
    "            if not queue:\n",
    "                pre[i]=-1\n",
    "            elif queue and queue[-1][0]<arr[i]:\n",
    "                pre[i]=queue[-1][1]\n",
    "            else:\n",
    "                pre[i]=i-1\n",
    "            queue.append((arr[i],i))\n",
    "        queue=[]\n",
    "        arr.reverse()\n",
    "        for i in range(len(arr)):\n",
    "            while queue and queue[-1][0]>arr[i]:\n",
    "                queue.pop()\n",
    "            if not queue:\n",
    "                lat[len(arr)-1-i]=len(arr)\n",
    "            elif queue and queue[-1][0]<=arr[i]:\n",
    "                lat[len(arr)-1-i]=len(arr)-1-queue[-1][1]\n",
    "            else:\n",
    "                lat[len(arr)-1-i]=len(arr)-i\n",
    "            queue.append((arr[i],i))\n",
    "        ans=0\n",
    "        # print(pre)\n",
    "        # print(lat)\n",
    "        arr.reverse()\n",
    "        for i in range(len(arr)):\n",
    "            ans+=(i-pre[i])*(lat[i]-i)*arr[i]\n",
    "            ans=int(ans%(1e9+7))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        # okay, we are having issues now\n",
    "        # using monostack, I think we can keep track of\n",
    "        # \"each number\"\n",
    "        n: int = len(arr)\n",
    "        nbigger: List[int] = [0] * n\n",
    "\n",
    "        i: int = 0; a: int = 0\n",
    "        stack: List[int] = []\n",
    "        for i, a in enumerate(arr):\n",
    "            # nbigger[i] = 0 if not i else nbigger[i-1]\n",
    "            while stack and stack[-1][0] > a:\n",
    "                _, prev_i = stack.pop(-1)\n",
    "                nbigger[i] = i - prev_i + nbigger[prev_i]\n",
    "            stack.append((a, i))\n",
    "        n_smaller_left = nbigger\n",
    "\n",
    "        right: List[int] = [0] * n\n",
    "        n_smaller_right = right\n",
    "        \n",
    "        rarr: List[int] = arr[::-1]\n",
    "        stack: List[int] = []\n",
    "        for i, a in enumerate(rarr):\n",
    "            # print(stack, \"with\", a)\n",
    "            while stack and stack[-1][0] >= a:\n",
    "                _, prev_i = stack.pop(-1)\n",
    "                right[i] = i - prev_i + right[prev_i]\n",
    "            stack.append((a, i))\n",
    "        right = right[::-1]\n",
    "\n",
    "        # [print(f\"{c}: {l} - {r}, added {c*((r + l) + r * l +1)}\") for i, (l, r, c) in enumerate(zip(n_smaller_left, right, arr))]\n",
    "        return sum(c*((r + l) + r * l +1) for l, r, c in zip(n_smaller_left, right, arr)) % (10**9+7)\n",
    "            \n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "\n",
    "        n: int = len(arr)\n",
    "        nbigger: List[int] = [0] * n\n",
    "\n",
    "        i: int = 0; a: int = 0\n",
    "        stack: List[int] = []\n",
    "        for i, a in enumerate(arr):\n",
    "            while stack and stack[-1][0] > a:\n",
    "                _, prev_i = stack.pop(-1)\n",
    "                nbigger[i] = i - prev_i + nbigger[prev_i]\n",
    "            stack.append((a, i))\n",
    "        n_smaller_left = nbigger\n",
    "\n",
    "        right: List[int] = [0] * n\n",
    "        n_smaller_right = right\n",
    "        \n",
    "        rarr: List[int] = arr[::-1]\n",
    "        stack: List[int] = []\n",
    "        for i, a in enumerate(rarr):\n",
    "            while stack and stack[-1][0] >= a:\n",
    "                _, prev_i = stack.pop(-1)\n",
    "                right[i] = i - prev_i + right[prev_i]\n",
    "            stack.append((a, i))\n",
    "        right = right[::-1]\n",
    "\n",
    "        return sum(c*((r + l) + r * l +1) for l, r, c in zip(n_smaller_left, right, arr)) % (10**9+7)\n",
    "            \n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        s = []\n",
    "        ans = 0\n",
    "        memo = [-1] * len(arr)\n",
    "        for i, num in enumerate(arr):\n",
    "            while s and s[-1][0] > num:\n",
    "                s.pop()\n",
    "            if not s:\n",
    "                memo[i] = (i + 1) * num\n",
    "            else:\n",
    "                memo[i] = (i - s[-1][1]) * num + memo[s[-1][1]]\n",
    "            ans += memo[i]\n",
    "            ans = ans % MOD\n",
    "            s.append((num, i))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        s = []\n",
    "        ans = 0\n",
    "        memo = [-1] * len(arr)\n",
    "        for i, num in enumerate(arr):\n",
    "            while s and s[-1][0] > num:\n",
    "                s.pop()\n",
    "            if not s:\n",
    "                memo[i] = (i + 1) * num\n",
    "            else:\n",
    "                memo[i] = (i - s[-1][1]) * num + memo[s[-1][1]]\n",
    "            ans += memo[i]\n",
    "            ans = ans % MOD\n",
    "            s.append((num, i))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10**9+7\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n, ans = len(arr), 0\n",
    "        sum = [0] * (n+1)\n",
    "        st = [[0, -1]]\n",
    "        for idx, it in enumerate(arr):\n",
    "            while st[-1][0] > it:\n",
    "                st.pop()\n",
    "            top, tid = st[-1]\n",
    "            st.append([it, idx])\n",
    "            sum[idx] = (sum[tid] + it * (idx - tid)) % mod\n",
    "            ans = (ans + sum[idx]) % mod\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def sumSubarrayMins(_, v):\n",
    "    v.append(0)\n",
    "    ans, i, a = 0, 0, 0\n",
    "    lo = [(0, 0)]\n",
    "    for j, b in enumerate(v, 1):\n",
    "      while a > b:\n",
    "        k, c = lo[i]\n",
    "        ans = (ans + a * (i - k) * (j - i)) % (10**9 + 7)\n",
    "        i, a = k, c\n",
    "      lo.append((i, a))\n",
    "      i, a = j, b\n",
    "    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    mod_number = 10 ** 9 + 7\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        arr_len = len(arr)\n",
    "        left = [0] * arr_len\n",
    "        right = [0] * arr_len\n",
    "        stack = [(float(\"-inf\"), -1)]\n",
    "        # 往右边遍历，每个idx的向左影响范围\n",
    "        for idx1 in range(arr_len):\n",
    "            v1 = arr[idx1]\n",
    "            # 保持栈单调递增，找到第一个小于当前idx1的下标\n",
    "            # idx1的影响范围为 \n",
    "            while stack and stack[-1][0] >= v1:\n",
    "                stack.pop()\n",
    "            left[idx1] += idx1 - stack[-1][1]\n",
    "            stack.append((v1, idx1))\n",
    "        stack = [(float(\"-inf\"), arr_len)]\n",
    "        for idx1 in range(arr_len - 1, -1, -1):\n",
    "            v1 = arr[idx1]\n",
    "            while stack and stack[-1][0] > v1:\n",
    "                stack.pop()\n",
    "            right[idx1] += stack[-1][1] - idx1\n",
    "            stack.append((v1, idx1))\n",
    "        ret = 0\n",
    "        for idx in range(arr_len):\n",
    "            ret += (left[idx] * right[idx] * arr[idx])\n",
    "        return ret % (self.mod_number)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "M = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        pair = [-1] * n\n",
    "        res = 0\n",
    "        for x, i in sorted(((x, i) for i, x in enumerate(arr)), reverse=True):\n",
    "            l = pair[i - 1] if i > 0 and pair[i - 1] != -1 else i\n",
    "            r = pair[i + 1] if i < n - 1 and pair[i + 1] != -1 else i\n",
    "            res += (i - l + 1) * (r - i + 1) * x\n",
    "            pair[l] = r\n",
    "            pair[r] = l\n",
    "        return res % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        preStack = [(-10**5,-1)]\n",
    "        preIdx = [-1]\n",
    "        for i in range(len(arr)):\n",
    "            while arr[i] <= preStack[-1][0]:\n",
    "                preStack.pop()\n",
    "            preIdx.append(preStack[-1][1])\n",
    "            preStack.append((arr[i],i))\n",
    "        \n",
    "        postStack = [(-10**5,len(arr))]\n",
    "        postIdx = [len(arr)]\n",
    "        for j in range(len(arr)-1,-1,-1):\n",
    "            while arr[j] < postStack[-1][0]:\n",
    "                postStack.pop()\n",
    "            postIdx.append(postStack[-1][1])\n",
    "            postStack.append((arr[j],j))\n",
    "        \n",
    "\n",
    "        ans = 0\n",
    "        p = 10**9 + 7\n",
    "        for k in range(1,len(preIdx)):\n",
    "            #print(k-preIdx[k]-1,postIdx[len(preIdx)-k] - k + 1)\n",
    "            a = (k-preIdx[k]-1)\n",
    "            b = (postIdx[len(preIdx)-k] - k + 1)\n",
    "            count = (a%p * b%p)%p\n",
    "            ans = ans + (count%p * arr[k-1]%p)%p\n",
    "        ans = ans % p\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        # 单调递增栈\n",
    "        MOD=10**9+7\n",
    "        n = len(arr)\n",
    "        st1, st2 = [], []\n",
    "        left,right=[],[]\n",
    "        for i in range(n):\n",
    "            c = 1\n",
    "            while st1 and st1[-1][0] >= arr[i]:\n",
    "                c += (st1.pop()[1])\n",
    "            st1.append((arr[i], c))\n",
    "            left.append(c)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            c = 1\n",
    "            while st2 and st2[-1][0] > arr[i]:\n",
    "                c += (st2.pop()[1])\n",
    "            st2.append((arr[i], c))\n",
    "            right.append(c)\n",
    "        right = right[::-1]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += arr[i] * left[i] * right[i]\n",
    "        return ans%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    mod_number = 10 ** 9 + 7\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        arr_len = len(arr)\n",
    "        left = [0] * arr_len\n",
    "        right = [0] * arr_len\n",
    "        # 5 3 1 2 4\n",
    "        # 1 2 3 4 5\n",
    "        stack = [(float(\"-inf\"), -1)]\n",
    "        # 往右边遍历，每个idx的向左影响范围\n",
    "        for idx1 in range(arr_len):\n",
    "            v1 = arr[idx1]\n",
    "            # 保持栈单调递增，找到第一个小于当前idx1的下标\n",
    "            # idx1的影响范围为 \n",
    "            while stack and stack[-1][0] >= v1:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[idx1] += idx1 - stack[-1][1]\n",
    "            stack.append((v1, idx1))\n",
    "        stack = [(float(\"-inf\"), arr_len)]\n",
    "        for idx1 in range(arr_len - 1, -1, -1):\n",
    "            v1 = arr[idx1]\n",
    "            while stack and stack[-1][0] > v1:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[idx1] += stack[-1][1] - idx1\n",
    "            stack.append((v1, idx1))\n",
    "        ret = 0\n",
    "        for idx in range(arr_len):\n",
    "            ret += (left[idx] * right[idx] * arr[idx])\n",
    "        return ret % (self.mod_number)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [0] * len(arr)\n",
    "        stack = [[0, -1]]\n",
    "\n",
    "        for i, v in enumerate(arr) :\n",
    "            while stack and stack[-1][0] > v :\n",
    "                stack.pop()\n",
    "            dp[i] = (v * (i - stack[-1][1]) + dp[stack[-1][1]]) % mod\n",
    "            stack.append([v, i])\n",
    "\n",
    "        return sum(dp) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def sumSubarrayMins(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        s = SortedList([-1, len(arr)])\n",
    "\n",
    "        for num, i in sorted((num, i) for i, num in enumerate(arr)):\n",
    "            idx = s.bisect_left(i)\n",
    "            ans = (ans + num * (i - s[idx - 1]) * (s[idx] - i)) % MOD\n",
    "            s.add(i)\n",
    "\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
